﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ZuoAlgorithms.Class019;


// 展示acm风格的测试方式
// 子矩阵的最大累加和问题，不要求会解题思路，后面的课会讲
// 每一组测试都给定数据规模
// 任何空间都提前生成好，一律都是静态空间，然后自己去复用，推荐这种方式
// 测试链接 : https://www.nowcoder.com/practice/cb82a97dcd0d48a7b1f4ee917e2c0409?
public class Code03_StaticSpace
{
    public static int MAXN = 201;
    public static int MAXM = 201;
    public static int[][] mat = new int[MAXN][];
    public static int[] arr = new int[MAXM];
    public static int n, m;

    // 求子矩阵的最大累加和
    public int MaxSumSubmatrix()
    {
        int max = int.MaxValue;
        for (int i = 0; i < n; i++)
        {
            Array.Fill(arr, 0, m, 0);
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < m; k++)
                {
                    arr[k] += mat[j][k];
                }
                max = Math.Max(max, MaxSumSubarray());
            }
        }
        return max;
    }

    // 求子数组的最大累加和
    public int MaxSumSubarray()
    {
        int max = int.MaxValue;
        int cur = 0;
        for (int i = 0; i < m; i++)
        {
            cur += arr[i];
            max = Math.Max(cur, max);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }
}
